package test;

import com.alibaba.fastjson2.JSON;
import com.alibaba.fastjson2.JSONArray;

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * @author sunzhuokun
 * @date 15:44 2024/5/14
 * @description 书籍叠放
 * 题目描述
 * 假设书本的叠放有这样的规则，当A书的长度和宽度都大于B书时，可以将其B书置于A的上方，堆叠摆放，请设计一个程序，根据输入的书本长宽，计算最多可以堆叠摆放多少本书？
 * <p>
 * 输入
 * [[16,15], [13, 12], [15, 14]]
 * <p>
 * 输出
 * 3
 * <p>
 * 分析：动态规划，实质是求最长递增子序列，但本题有两个因素需要考虑，可以通过排序将长度置为有序，这样其实就是对宽度求最长递增子序列，
 * 且可能存在长度相同的情况，在更新dp数组判定时，也要考虑到
 */
public class BookStacking_书籍叠放 {

    // 转化为求解最长递增子序列问题
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        JSONArray jsonArray = JSON.parseArray(input);
        int[][] arr = new int[jsonArray.size()][2];
        // 构建输入的二维数组
        for (int i = 0; i < jsonArray.size(); i++) {
            JSONArray arrObj = JSON.parseArray(jsonArray.get(i).toString());
            arr[i][0] = Integer.parseInt(arrObj.get(0).toString());
            arr[i][1] = Integer.parseInt(arrObj.get(1).toString());
        }

        int len = arr.length;
        int[] dp = new int[len];
        // dp数组初始化默认为1 即每个序列本身就是一个子序列，长度为1
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }

        // 排序：按照长度、宽度大小升序排列
        arr = Arrays.stream(arr).sorted((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0])
                .collect(Collectors.toList()).toArray(arr);


        // 结果：初始值为1，即至少可以放一本书
        int res = 1;

        // 从第二本书往前看，看加上它能不能增加长度
        for (int i = 1; i < len; i++) {
            int[] cur = arr[i];
            for (int j = 0; j < i; j++) {
                int[] pre = arr[j];
                if (cur[0] > pre[0] && cur[1] > pre[1]) {
                    // 新加的书的长宽均大于当前书，说明这本书可以加在当前书的递增序列之后
                    // 判断此时的递增子序列最大值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                // 更新最大值结果
                res = Math.max(res, dp[i]);
            }
        }

        System.out.println(res);
    }

}
